Given an integer array nums and two integers lower and upper, return the number of range sums that lie in[lower, upper]inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
Input: nums = [-2,5,-1], lower = -2, upper = 2 Output: 3 Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.
Input: nums = [0], lower = 0, upper = 0 Output: 1
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1-105 <= lower <= upper <= 105- The answer is guaranteed to fit in a 32-bit integer.
fromsortedcontainersimportSortedListclassSolution: defcountRangeSum(self, nums: List[int], lower: int, upper: int) ->int: prefixsums=SortedList([0]) prefixsum=0ret=0foriinrange(len(nums)): prefixsum+=nums[i] j=prefixsums.bisect_right(prefixsum-lower) k=prefixsums.bisect_left(prefixsum-upper) ret+=j-kprefixsums.add(prefixsum) returnret